package com.jsy.common.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class MedianFinder {
    private PriorityQueue<Integer> queueMin;
    private PriorityQueue<Integer> queueMax;
    public MedianFinder() {
        queueMin = new PriorityQueue<>((o1, o2) -> o2-o1);
        queueMax = new PriorityQueue<>(((o1, o2) -> o1-o2));
    }
    
    public void addNum(int num) {
        if (queueMin.size()==0){
            queueMin.add(num);
            return;
        }
        if (num>queueMin.peek()){
            queueMax.add(num);
        }else {
            queueMin.add(num);
        }
        while (queueMax.size()>queueMin.size()){
            queueMin.add(queueMax.poll());
        }
        while (queueMin.size()>queueMax.size()+1){
            queueMax.add(queueMin.poll());
        }
    }
    
    public double findMedian() {
        if (queueMin.isEmpty()){
            return 0;
        }
        if (!queueMax.isEmpty() && queueMin.size() == queueMax.size()){
            return (queueMin.peek()+queueMax.peek())/2.0;
        }else if (queueMin.size()>queueMax.size()){
            return queueMin.peek();
        }
        return 0;
    }
}
